package com.mlh.backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Stream;

/**
 * @author 缪林辉
 * @date 2024/4/5 10:05
 * @DESCRIPTION
 */

// 给定一个候选人编号的集合 candidates 和一个目标数 target ，
// 找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的每个数字在每个组合中只能使用 一次 。
// 注意：解集不能包含重复的组合。
public class 组合总和2 {
    //大部分自己写出,但是核心代码是看随想录中的解说想通写出来的
    //但是剪枝操作没做好,导致执行时间过长
    //因此组合题目要好好剪枝
    LinkedList<Integer>path=new LinkedList<>();
    List<List<Integer>>res=new ArrayList<>();
    public List<List<Integer>> method1(int[] candidates, int target) {
        //对candidates数组进行排序
        Arrays.sort(candidates);
        recursion(0,candidates,target);
        return res;
    }

    public void recursion(int head,int[] candidates,int differ){
        if(head>=candidates.length||differ<=0){//differ<0 也返回  剪枝操作
            if(differ==0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = head; i < candidates.length; i++) {
            //这里i>head 不能是i>0,这样的话往深度走的时候，i=head 和 head-1 位置上的元素作比较
            //产生重复就会跳过，然而head-1 是不应该被比较的
            if(i>head&&candidates[i-1]==candidates[i]){
                continue;
            }
            path.add(candidates[i]);
            recursion(i+1,candidates,differ-candidates[i]);
            path.removeLast();
            //剪枝操作
            if(differ-candidates[i]<=0){
                break;
            }
        }
    }

    public List<List<Integer>> practice(int[] candidates, int target) {
        Arrays.sort(candidates);
        recursionPractice(candidates,target,0);
        return res;
    }

    public void recursionPractice(int[] candidates, int target,int startIndex){
        if(target<=0){
            if(target==0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if(i>startIndex&&candidates[i-1]==candidates[i]){//写这个判断条件的时候，只需要在一个节点上去思考即可，不要想到下一层
                continue;
            }
            if(candidates[i]>target){//利用排序，进行剪枝
                return;
            }
            path.add(candidates[i]);
            recursionPractice(candidates,target-candidates[i],i+1);
            path.removeLast();
        }
    }
}
